package pers.qianyu.month_202101.date_20210109;

/**
 * 10. 正则表达式匹配
 * https://leetcode-cn.com/problems/regular-expression-matching/
 * [没搞懂]
 *
 * @author mizzle rain
 * @date 2021-01-09 15:44
 */
public class IsMatch {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        s = " " + s;
        p = " " + p;
        boolean[][] dp = new boolean[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0 && j == 0) {
                    dp[0][0] = true;
                } else {
                    if (j + 1 <= n && p.charAt(j + 1) == '*')
                        continue;
                    if (p.charAt(j) != '*') {
                        if (p.charAt(j) == '.' || p.charAt(j) == s.charAt(i))
                            if (i > 0 && j > 0)
                                dp[i][j] = dp[i - 1][j - 1];
                    } else {
                        if (j >= 2)
                            dp[i][j] = dp[i][j - 2];
                        if (i > 0 && j > 0)
                            if (p.charAt(j - 1) == s.charAt(i) || p.charAt(j - 1) == '.')
                                if (dp[i - 1][j]) dp[i][j] = true;
                    }
                }
            }
        }
        return dp[m][n];
    }
}
